function swap(arr, i, j) {
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
/**
 * 1.电话号码的字母组合
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 * 九宫格输入法
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    let map = {
        '2': ['a', 'b', 'c'],
        '3': ['d', 'e', 'f'],
        '4': ['g', 'h', 'i'],
        '5': ['j', 'k', 'l'],
        '6': ['m', 'n', 'o'],
        '7': ['p', 'q', 'r', 's'],
        '8': ['t', 'u', 'v'],
        '9': ['w', 'x', 'y', 'z']
    };
    let rtn = [];
    for (const c of digits) {
        if (rtn.length) {
            let size = rtn.length;
            let arr = map[c];
            while (size--) {
                let pre = rtn.shift();
                for (const item of arr) {
                    rtn.push(pre + item);
                }
            }
        } else {
            rtn.push(...map[c]);
        }
    }
    return rtn;
};
/**
 * #
 * 2.括号生成器
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * 有效括号组合需满足：左括号必须以正确的顺序闭合。
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    let ans = [];
    function backtrack(ans, cur, open, close, max) {
        if (open === max && close === max) {
            ans.push(cur);
            return;
        }
        if (open < max) {
            backtrack(ans, cur + '(', open + 1, close, max);
        }
        if (close < open) {
            backtrack(ans, cur + ')', open, close + 1, max);
        }
    }
    backtrack(ans, '', 0, 0, n);
    return ans;
};
// console.log('generateParenthesis', generateParenthesis(3));
/**
 * 3.全排列
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    let rtn = [];
    function backtrack(nums, rtn, first) {
        if (first === nums.length) {
            // 复制一条结果，并保存到结果集中
            rtn.push(Array.from(nums));
            return;
        }
        // 技巧：通过交换元素，实现通过边界i区分已使用过元素和未使用过元素
        // 之后通过再次交换元素重置数组原来的状态
        for (let i = first; i < nums.length; i++) {
            swap(nums, first, i);
            backtrack(nums, rtn, first + 1);
            swap(nums, first, i);
        }
    }
    backtrack(nums, rtn, 0);
    return rtn;
};
// console.log('permute:', permute([1,2,3]));
/**
 * 4.子集
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    let res = [];
    function backtrack(nums, tar, res, first) {
        res.push(Array.from(tar));
        if (first === nums.length) {
            return;
        }
        for (let i = first; i < nums.length; i++) {
            tar.push(nums[i]);
            backtrack(nums, tar, res, i + 1);
            tar.pop();
        }
    }
    backtrack(nums, [], res, 0);
    return res;
};
// console.log('subsets:', subsets([1,2,3]));
/**
 * 5.单词搜索
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    let rows = board.length,
        cols = board[0].length;
    function dfs(grid, i, j, mark, word, index) {
        if (i < 0 || j < 0 || i >= rows || j >= cols) {
            return false;
        }
        let key = i + '_' + j;
        if (grid[i][j] === word[index] && !mark[key]) {
            ++index
            if (index === word.length) {
                return true;
            }
            mark[key] = true;
            let top = dfs(grid, i - 1, j, mark, word, index); // 上
            let bottom = dfs(grid, i + 1, j, mark, word, index); // 下
            let left = dfs(grid, i, j - 1, mark, word, index); // 左
            let right = dfs(grid, i, j + 1, mark, word, index); // 右
            delete mark[key];
            return top || bottom || left || right;
        }
        return false;
    }
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (dfs(board, i, j, {}, word, 0)) {
                return true;
            }
        }
    }
    return false;
};
// console.log('exist:', exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "SEE"));  // true
// console.log('exist:', exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCB")); // false
